package com.sheng.leetcode.year2023.month03.day24;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/03/24
 * <p>
 * 1032. 字符流<p>
 * <p>
 * 设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。<p>
 * 例如，words = ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 'a'、'x'、'y' 和 'z' ，<p>
 * 你所设计的算法应当可以检测到 "axyz" 的后缀 "xyz" 与 words 中的字符串 "xyz" 匹配。<p>
 * 按下述要求实现 StreamChecker 类：<p>
 * StreamChecker(String[] words) ：构造函数，用字符串数组 words 初始化数据结构。<p>
 * boolean query(char letter)：从字符流中接收一个新字符，<p>
 * 如果字符流中的任一非空后缀能匹配 words 中的某一字符串，返回 true ；否则，返回 false。<p>
 * <p>
 * 示例：<p>
 * 输入：<p>
 * ["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]<p>
 * [[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]<p>
 * 输出：<p>
 * [null, false, false, false, true, false, true, false, false, false, false, false, true]<p>
 * 解释：<p>
 * StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);<p>
 * streamChecker.query("a"); // 返回 False<p>
 * streamChecker.query("b"); // 返回 False<p>
 * streamChecker.query("c"); // 返回 False<p>
 * streamChecker.query("d"); // 返回 True ，因为 'cd' 在 words 中<p>
 * streamChecker.query("e"); // 返回 False<p>
 * streamChecker.query("f"); // 返回 True ，因为 'f' 在 words 中<p>
 * streamChecker.query("g"); // 返回 False<p>
 * streamChecker.query("h"); // 返回 False<p>
 * streamChecker.query("i"); // 返回 False<p>
 * streamChecker.query("j"); // 返回 False<p>
 * streamChecker.query("k"); // 返回 False<p>
 * streamChecker.query("l"); // 返回 True ，因为 'kl' 在 words 中<p>
 * <p>
 * 提示：<p>
 * 1 <= words.length <= 2000<p>
 * 1 <= words[i].length <= 200<p>
 * words[i] 由小写英文字母组成<p>
 * letter 是一个小写英文字母<p>
 * 最多调用查询 4 * 10^4 次<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/stream-of-characters">1032. 字符流</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1032 {

    @Test
    public void test01() {
        StreamChecker streamChecker = new StreamChecker(new String[]{"cd", "f", "kl"});
        System.out.println(streamChecker.query('a')); // 返回 False
        System.out.println(streamChecker.query('b')); // 返回 False
        System.out.println(streamChecker.query('c')); // 返回 False
        System.out.println(streamChecker.query('d')); // 返回 True ，因为 'cd' 在 words 中
        System.out.println(streamChecker.query('e')); // 返回 False
        System.out.println(streamChecker.query('f')); // 返回 True ，因为 'f' 在 words 中
        System.out.println(streamChecker.query('g')); // 返回 False
        System.out.println(streamChecker.query('h')); // 返回 False
        System.out.println(streamChecker.query('i')); // 返回 False
        System.out.println(streamChecker.query('j')); // 返回 False
        System.out.println(streamChecker.query('k')); // 返回 False
        System.out.println(streamChecker.query('l')); // 返回 True ，因为 'kl' 在 words 中
    }
}

//我们可以根据初始化时的字符串数组 words 构建前缀树，前缀树的每个节点包含两个属性：
//children：指向 26 个字母的指针数组，用于存储当前节点的子节点。
//is_end：标记当前节点是否为某个字符串的结尾。
//在构造函数中，我们遍历字符串数组 words，对于每个字符串 w，我们将其反转后，逐个字符插入到前缀树中，插入结束后，将当前节点的 is_end 标记为 true。
//在 query 函数中，我们将当前字符 c 加入到字符流中，然后从后往前遍历字符流，对于每个字符c，我们在前缀树中查找是否存在以 c 为结尾的字符串，
//如果存在，返回 true，否则返回 false。注意到 words 中的字符串长度不超过 200，因此查询时最多只需要遍历 200 个字符。
//
class Trie {
    Trie[] children = new Trie[26];
    boolean isEnd = false;

    public void insert(String w) {
        Trie node = this;
        // 从字符串的最后一位开始进行遍历
        for (int i = w.length() - 1; i >= 0; --i) {
            // 获取该字符对应的值
            int idx = w.charAt(i) - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean query(StringBuilder s) {
        Trie node = this;
        for (int i = s.length() - 1, j = 0; i >= 0 && j < 201; --i, ++j) {
            int idx = s.charAt(i) - 'a';
            if (node.children[idx] == null) {
                return false;
            }
            node = node.children[idx];
            if (node.isEnd) {
                return true;
            }
        }
        return false;
    }
}

class StreamChecker {
    private StringBuilder sb = new StringBuilder();
    private Trie trie = new Trie();

    public StreamChecker(String[] words) {
        for (String w : words) {
            trie.insert(w);
        }
    }

    public boolean query(char letter) {
        sb.append(letter);
        return trie.query(sb);
    }
}
//作者：lcbin
//链接：https://leetcode.cn/problems/stream-of-characters/solution/python3javacgo-yi-ti-yi-jie-qian-zhui-sh-79kg/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

// 暴力破解，超时
//class StreamChecker {
//
//    List<String> list;
//
//    StringBuilder str = new StringBuilder("");
//
//    public StreamChecker(String[] words) {
//        list = Arrays.stream(words).collect(Collectors.toList());
//    }
//
//    public boolean query(char letter) {
//        str.append(letter);
//        for (String s : list) {
//            if (str.indexOf(s) != -1 && str.lastIndexOf(s) + s.length() == str.length()) {
//                return true;
//            }
//        }
//        return false;
//    }
//}

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker obj = new StreamChecker(words);
 * boolean param_1 = obj.query(letter);
 */
